class Solution {
public:
    unordered_map<Node*,Node*> cachenode;
    Node* copyRandomList(Node* head) {
        if(!head) return nullptr;
        if(!cachenode.count(head))
        {
            Node *headNew=new Node(head->val);
            cachenode[head]=headNew;
            headNew->next=copyRandomList(head->next);
            headNew->random=copyRandomList(head->random);
        }
        return cachenode[head];
    }
};
